package com.wtgroup.demo.mianshi.算法.动态规划.暴力递归;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tuple2;

/**
 * A先手,B后手, 每次只能取最左或最右的纸牌.
 * 看谁获得分数最大, 返回获胜者的分数
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/8 0:05
 */
public class Q_取纸牌分数最大 {

    public static void main(String[] args) {
        Judger.of(() -> {
            int[] arr = RandomUtil.randomArray(RandomUtil.randomInt(0, 10), 0, 1000);
            int[] res = D1_dp.func(arr);
            return Math.max(res[0], res[1]) == Code02_CardsInLine.win1(arr);
            // System.out.println(Code02_CardsInLine.win1(arr));
            // return true;
        }).setIterCount(1000).start().print();
    }

    // 我的思路
    static class D1 {

        static int[] func(int[] arr) {
            if (arr == null || arr.length == 0) {
                return new int[]{0, 0};
            }
            int[] a = A(arr, 0, arr.length - 1);
            // return Math.max(a[0], a[1]);
            return a;
        }


        // [L,R] 区间的牌, A 先手, 他会想法设法让自己的大,B的小, B 也是这么想
        private static int[] A(int[] arr, int L, int R) {
            if (L >= R) {
                return new int[]{arr[L], 0};
            }

            // 可能性1: 取 L, 剩下的, B 取, B 尽可能让A小, 让他大
            int[] tup1 = B(arr, L + 1, R);
            // 可能性2: 取 R
            int[] tup2 = B(arr, L, R - 1);

            // ? 应该不会出现零和博弈吧. 即, 某个可能性中, A拿到的和B拿到的都更小
            if (arr[L] + tup1[0] > arr[R] + tup2[0]) {
                return new int[]{arr[L] + tup1[0], tup1[1]};
            } else {
                return new int[]{arr[R] + tup2[0], tup2[1]};
            }
        }

        private static int[] B(int[] arr, int L, int R) {
            if (L >= R) {
                return new int[]{0, arr[L]};
            }

            // 可能性1
            int[] tup1 = A(arr, L + 1, R);
            // 可能性2
            int[] tup2 = A(arr, L, R - 1);

            if (arr[L] + tup1[1] > arr[R] + tup2[1]) {
                return new int[]{tup1[0], arr[L] + tup1[1]};
            } else {
                return new int[]{tup2[0], arr[R] + tup2[1]};
            }
        }
    }

    static class D1_dp {
        static int[] func(int[] arr) {
            if (arr == null || arr.length == 0) {
                return new int[]{0, 0};
            }

            int N = arr.length;
            Tuple2<Integer, Integer>[][] dp_a = new Tuple2[N][N];
            Tuple2<Integer, Integer>[][] dp_b = new Tuple2[N][N];

            for (int L = N - 1; L >= 0; L--) {
                for (int R = 0; R < N; R++) {
                    A(arr, L, R, dp_a, dp_b);
                }
            }

            Tuple2<Integer, Integer> res = dp_a[0][N - 1];
            return new int[]{res.getFirst(), res.getSecond()};
        }

        private static void A(int[] arr, int L, int R, Tuple2<Integer, Integer>[][] dp_a, Tuple2<Integer, Integer>[][] dp_b) {
            if (L >= R) {
                dp_a[L][R] = new Tuple2(arr[L], 0);
                return;
            }

            // 可能性1: 取 L, 剩下的, B 取, B 尽可能让A小, 让他大
            B(arr, L + 1, R, dp_a, dp_b);
            Tuple2<Integer, Integer> tup1 = dp_b[L + 1][R]; // B(arr, L + 1, R);
            // 可能性2: 取 R
            B(arr, L, R - 1, dp_a, dp_b);
            Tuple2<Integer, Integer> tup2 = dp_b[L][R - 1]; // B(arr, L, R - 1);

            // ? 应该不会出现零和博弈吧. 即, 某个可能性中, A拿到的和B拿到的都更小
            if (arr[L] + tup1.getFirst() > arr[R] + tup2.getFirst()) {
                // return new int[]{arr[L] + tup1[0], tup1[1]};
                dp_a[L][R] = new Tuple2<>(arr[L] + tup1.getFirst(), tup1.getSecond());
            } else {
                // return new int[]{arr[R] + tup2[0], tup2[1]};
                dp_a[L][R] = new Tuple2<>(arr[R] + tup2.getFirst(), tup2.getSecond());
            }
        }

        private static void B(int[] arr, int L, int R, Tuple2<Integer, Integer>[][] dp_a, Tuple2<Integer, Integer>[][] dp_b) {
            if (L >= R) {
                // return new int[]{0, arr[L]};
                dp_b[L][R] = new Tuple2(0, arr[L]);
                return;
            }

            // 可能性1
            // int[] tup1 = A(arr, L + 1, R);
            A(arr, L + 1, R, dp_a, dp_b);
            Tuple2<Integer, Integer> tup1 = dp_a[L + 1][R];
            // 可能性2
            // int[] tup2 = A(arr, L, R - 1);
            A(arr, L, R - 1, dp_a, dp_b);
            Tuple2<Integer, Integer> tup2 = dp_a[L][R - 1];

            if (arr[L] + tup1.getSecond() > arr[R] + tup2.getSecond()) {
                dp_b[L][R] =  new Tuple2<>(tup1.getFirst(), arr[L] + tup1.getSecond());
            } else {
                dp_b[L][R] = new Tuple2<>(tup2.getFirst(), arr[R] + tup2.getSecond());
            }
        }
    }

    public static class Code02_CardsInLine {

        // 根据规则，返回获胜者的分数
        public static int win1(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            int first = f1(arr, 0, arr.length - 1);
            int second = g1(arr, 0, arr.length - 1);
            return Math.max(first, second);
        }

        // arr[L..R]，先手获得的最好分数返回
        public static int f1(int[] arr, int L, int R) {
            if (L == R) {
                return arr[L];
            }
            int p1 = arr[L] + g1(arr, L + 1, R);
            int p2 = arr[R] + g1(arr, L, R - 1);
            return Math.max(p1, p2);
        }

        // // arr[L..R]，后手获得的最好分数返回
        public static int g1(int[] arr, int L, int R) {
            if (L == R) {
                return 0;
            }
            int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
            int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
            return Math.min(p1, p2);
        }

        public static int win2(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            int N = arr.length;
            int[][] fmap = new int[N][N];
            int[][] gmap = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    fmap[i][j] = -1;
                    gmap[i][j] = -1;
                }
            }
            int first = f2(arr, 0, arr.length - 1, fmap, gmap);
            int second = g2(arr, 0, arr.length - 1, fmap, gmap);
            return Math.max(first, second);
        }

        // arr[L..R]，先手获得的最好分数返回
        public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
            if (fmap[L][R] != -1) {
                return fmap[L][R];
            }
            int ans = 0;
            if (L == R) {
                ans = arr[L];
            } else {
                int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
                int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
                ans = Math.max(p1, p2);
            }
            fmap[L][R] = ans;
            return ans;
        }

        // // arr[L..R]，后手获得的最好分数返回
        public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
            if (gmap[L][R] != -1) {
                return gmap[L][R];
            }
            int ans = 0;
            if (L != R) {
                int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
                int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
                ans = Math.min(p1, p2);
            }
            gmap[L][R] = ans;
            return ans;
        }

        public static int win3(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            int N = arr.length;
            int[][] fmap = new int[N][N];
            int[][] gmap = new int[N][N];
            for (int i = 0; i < N; i++) {
                fmap[i][i] = arr[i];
            }
            for (int startCol = 1; startCol < N; startCol++) {
                int L = 0;
                int R = startCol;
                while (R < N) {
                    fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                    gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                    L++;
                    R++;
                }
            }
            return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
        }
        //
        // public static void main(String[] args) {
        //     int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
        //     System.out.println(win1(arr));
        //     System.out.println(win2(arr));
        //     System.out.println(win3(arr));
        //
        // }

    }
}
